package codetop.microsoft.T173;

import util.TreeNode;

import java.util.Deque;
import java.util.LinkedList;

class BSTIterator {

    private TreeNode cur;
    private Deque<TreeNode> dq = new LinkedList<>();

    public BSTIterator(TreeNode root) {
        cur = root;
    }

    public int next() {
        while (cur != null) {
            dq.push(cur);
            cur = cur.left;
        }
        cur = dq.pop();
        int v = cur.val;
        cur = cur.right;
        return v;
    }

    public boolean hasNext() {
        return !(dq.isEmpty() && cur == null);
    }
}